﻿using Microsoft.VisualBasic;
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Text;
using System.Threading.Tasks;

namespace CSLearn
{
    public class Backtrack
    {

        public IList<IList<int>> Subsets(int[] nums)
        {
            IList<IList<int>> res = new List<IList<int>>();
            Stack<int> path = new Stack<int>();
            res.Add(new List<int>());
            BackSubsets(res, path, nums, 0);
            return res;
        }

        void BackSubsets(IList<IList<int>> res, Stack<int> path, int[] nums, int index)
        {
            if (index == nums.Length - 1)
            {
                res.Add(new List<int>(path));
                return;
            }
            for (int i = index; i < nums.Length; i++)
            {
                path.Push(nums[i]);
                BackSubsets(res, path, nums, index + 1);
                path.Pop();
            }
        }

        bool[] usedColQueen, used135Queen, used45Queen;
        /// <summary>
        /// leetcode  51  N皇后(回溯)
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public IList<IList<string>> SolveNQueens(int n)
        {
            IList<IList<string>> res = new List<IList<string>>();
            int[] board = new int[n];
            usedColQueen = new bool[n];
            used45Queen = new bool[2 * n - 1];
            used135Queen = new bool[2 * n - 1];
            BackSloveNQueens(res, board, n, 0);
            return res;
        }

        void BackSloveNQueens(IList<IList<string>> res, int[] board, int n, int row)
        {
            if (row == n)
            {
                List<string> temp = new List<string>();
                foreach (int col in board)
                {
                    char[] str = new char[n];
                    Array.Fill(str, '.');
                    str[col] = 'Q';
                    temp.Add(new string(str));
                }
                res.Add(temp);
            }
            for (int i = 0; i < n; i++)
            {
                if (usedColQueen[i] || used45Queen[row + i] || used135Queen[row - i + n - 1])
                    continue;
                board[row] = i;
                usedColQueen[i] = true;
                used45Queen[row + i] = true;
                used135Queen[row - i + n - 1] = true;
                BackSloveNQueens(res, board, n, row + 1);
                usedColQueen[i] = false;
                used45Queen[row + i] = false;
                used135Queen[row - i + n - 1] = false;

            }
        }


        /// <summary>
        /// leetcode  216  组合总和3(回溯)
        /// </summary>
        /// <param name="k"></param>
        /// <param name="n"></param>
        /// <returns></returns>
        public IList<IList<int>> CombinationSum3(int k, int n)
        {
            IList<IList<int>> res = new List<IList<int>>();
            IList<int> path = new List<int>();
            BacktrackCombinationSum3(res, path, k, n, 1);
            return res;
        }

        void BacktrackCombinationSum3(IList<IList<int>> res, IList<int> path, int k, int n, int index)
        {
            if (n <= 0 || k == 0)
            {
                if (n == 0 && k == 0)
                    res.Add(new List<int>(path));

                return;
            }
            for (int i = index; i < 10; i++)
            {
                path.Add(i);
                BacktrackCombinationSum3(res, path, k - 1, n - i, index + 1);
                path.Remove(i);
            }
        }

        /// <summary>
        /// leetcode  46  全排列(回溯)
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public IList<IList<int>> Permute(int[] nums)
        {
            IList<IList<int>> res = new List<IList<int>>();
            IList<int> path = new List<int>();
            bool[] used = new bool[nums.Length];
            BacktrackPermute(res, path, used, nums);
            return res;
        }

        void BacktrackPermute(IList<IList<int>> res, IList<int> path, bool[] used, int[] nums)
        {
            if (path.Count == nums.Length)
            {
                res.Add(new List<int>(path));
                return;
            }
            for (int i = 0; i < nums.Length; i++)
            {
                if (!used[i])
                {
                    path.Add(nums[i]);
                    used[i] = true;
                    BacktrackPermute(res, path, used, nums);
                    path.Remove(nums[i]);
                    used[i] = false;
                }
            }
        }

        /// <summary>
        /// leetcode  77  组合(回溯)
        /// </summary>
        /// <param name="n"></param>
        /// <param name="k"></param>
        /// <returns></returns>
        public IList<IList<int>> Combine(int n, int k)
        {
            IList<IList<int>> res = new List<IList<int>>();
            IList<int> path = new List<int>();
            BacktrackCombine(res, path, n, k, 1);
            return res;
        }

        void BacktrackCombine(IList<IList<int>> res, IList<int> path, int n, int k, int start)
        {
            if (path.Count == k)
            {
                res.Add(new List<int>(path));
                return;
            }
            for (int i = start; i <= n; i++)
            {
                path.Add(i);
                BacktrackCombine(res, path, n, k, i + 1);
                path.Remove(i);
            }
        }

        /// <summary>
        /// leetcode  2698  求一个整数的惩罚数(回溯)
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public int PunishmentNumber(int n)
        {
            int res = 0;
            for (int i = 1; i <= n; i++)
            {
                string s = (i * i).ToString();
                if (BacktrackPunishmentNumber(s, 0, 0, i)) res += i * i;
            }
            return res;
        }

        bool BacktrackPunishmentNumber(string s, int index, int sum, int target)
        {
            if (index == s.Length) return sum == target;
            int nextSum = 0;
            for (int i = index; i < s.Length; i++)
            {
                nextSum = nextSum * 10 + s[i] - '0';
                if (nextSum + sum > target) break;
                if (BacktrackPunishmentNumber(s, i + 1, nextSum + sum, target)) return true;
            }
            return false;
        }


        /// <summary>
        /// leetcode  37  解数独(回溯)
        /// </summary>
        /// <param name="board"></param>
        public void SolveSudoku(char[][] board)
        {
            BacktrackSolveSudoku(board);
        }

        bool BacktrackSolveSudoku(char[][] board)
        {
            for (int i = 0; i < 9; i++)     // 遍历行
            {
                for (int j = 0; j < 9; j++)     // 遍历列
                {
                    // 跳过原始数字
                    if (board[i][j] != '.') continue;

                    // 逐个数字尝试放入
                    for (char val = '1'; val <= '9'; val++)
                    {
                        // 如果合适，放入
                        if (IsVaildOld(board, val, i, j))
                        {
                            board[i][j] = val;

                            // 如果找到合适一组，返回
                            if (BacktrackSolveSudoku(board)) return true;

                            // 回溯本次的放入操作
                            board[i][j] = '.';
                        }
                    }
                    // 9个数都试完了，都不行，那么就返回false
                    return false;
                    // 因为如果一行一列确定下来了，这里尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解！
                    // 那么会直接返回， 「这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去！」
                }
            }
            // 遍历完没有返回false，说明找到了合适棋盘位置了
            return true;
        }

        /// <summary>
        /// 判断放入数字是否合适
        /// </summary>
        /// <param name="board"></param>
        /// <param name="val"></param>
        /// <param name="row"></param>
        /// <param name="col"></param>
        /// <returns></returns>
        bool IsVaildOld(char[][] board, char val, int row, int col)
        {
            for (int i = 0; i < 9; i++)     // 判断同列是否重复
            {
                if (board[i][col] == val) return false;
            }
            for (int i = 0; i < 9; i++)     // 判断同行是否重复
            {
                if (board[row][i] == val) return false;
            }

            // 判断九宫格是否重复
            int startRow = (row / 3) * 3;
            int startCol = (col / 3) * 3;
            for (int i = startRow; i < startRow + 3; i++)
            {
                for (int j = startCol; j < startCol + 3; j++)
                {
                    if (board[i][j] == val) return false;
                }
            }
            return true;
        }


        bool[] usedCol, usedDiag45, usedDiag135;

        /// <summary>
        /// leetcode  51  N皇后(回溯)Old
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public IList<IList<string>> SolveNQueensOld(int n)
        {
            IList<IList<string>> res = new List<IList<string>>();
            usedCol = new bool[2 * n - 1];
            usedDiag45 = new bool[2 * n - 1];
            usedDiag135 = new bool[2 * n - 1];
            int[] board = new int[n];

            BacktrackSolveNQueensOld(res, board, n, 0);
            return res;
        }

        void BacktrackSolveNQueensOld(IList<IList<string>> res, int[] board, int n, int row)
        {
            if (row == n)
            {
                List<string> temp = new List<string>();
                foreach (int col in board)
                {
                    char[] str = new char[n];
                    Array.Fill(str, '.');
                    str[col] = 'Q';
                    temp.Add(new string(str));
                }
                res.Add(temp);
                return;
            }
            for (int col = 0; col < n; col++)
            {
                if (usedCol[col] || usedDiag45[row + col] || usedDiag135[row - col + n - 1])
                    continue;
                board[row] = col;
                usedCol[col] = true;
                usedDiag45[row + col] = true;
                usedDiag135[row - col + n - 1] = true;
                BacktrackSolveNQueensOld(res, board, n, row + 1);
                usedCol[col] = false;
                usedDiag45[row + col] = false;
                usedDiag135[row - col + n - 1] = false;
            }
        }

        bool IsValidQueen(char[][] grid, int row, int col)
        {
            // 检查列
            for (int i = 0; i < row; i++)
            {
                if (grid[i][col] == 'Q') return false;
            }
            for (int i = 0; i < 0; i++)
            {

            }

            return true;
        }

        /// <summary>
        /// leetcode  332  重新安排行程(回溯)
        /// </summary>
        /// <param name="tickets"></param>
        /// <returns></returns>
        public IList<string> FindItinerary(IList<IList<string>> tickets)
        {
            List<string> res = new List<string>();
            List<string> path = new List<string>();
            List<IList<string>> sortList = tickets.ToList();
            sortList.Sort((a, b) => a[0].CompareTo(b[0]));

            bool[] used = new bool[sortList.Count];
            path.Add("JFK");
            BacktrackFindItinerary(sortList, res, path, used);

            return res;
        }

        bool BacktrackFindItinerary(List<IList<string>> sortList, List<string> res, List<string> path, bool[] used)
        {
            if (path.Count == sortList.Count + 1)
            {
                res = new List<string>(path);
                return true;
            }

            for (int i = 0; i < sortList.Count; i++)
            {
                if (!used[i] && path[path.Count - 1].Equals(sortList[i][0]))
                {
                    path.Add(sortList[i][1]);
                    used[i] = true;

                    if (BacktrackFindItinerary(sortList, res, path, used))
                        return true;

                    used[i] = false;
                    path.RemoveAt(path.Count - 1);
                }
            }
            return false;
        }

        /// <summary>
        /// leetcode  47  全排列2(回溯)
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public IList<IList<int>> PermuteUnique(int[] nums)
        {
            IList<IList<int>> res = new List<IList<int>>();
            if (nums.Length == 0) return res;
            Array.Sort(nums);
            BacktrackPermuteUnique(res, new List<int>(), new bool[nums.Length], nums);

            return res;
        }

        void BacktrackPermuteUnique(IList<IList<int>> res, List<int> path, bool[] visited, int[] nums)
        {
            if (path.Count == nums.Length)
            {
                res.Add(new List<int>(path));
                return;
            }

            for (int i = 0; i < nums.Length; i++)
            {
                if (i > 0 && nums[i - 1] == nums[i] && visited[i - 1])
                    continue;

                if (!visited[i])
                {
                    visited[i] = true;
                    path.Add(nums[i]);
                    BacktrackPermuteUnique(res, path, visited, nums);
                    path.RemoveAt(path.Count - 1);
                    visited[i] = false;
                }
            }
        }

        /// <summary>
        /// leetcode  46  全排列(回溯)
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public IList<IList<int>> PermuteOld(int[] nums)
        {
            IList<IList<int>> res = new List<IList<int>>();

            BacktrackPermute(res, new List<int>(), new bool[nums.Length], nums);
            return res;
        }

        void BacktrackPermute(IList<IList<int>> res, List<int> path, bool[] visited, int[] nums)
        {
            if (path.Count == nums.Length)
            {
                res.Add(new List<int>(path));
                return;
            }
            for (int i = 0; i < nums.Length; i++)
            {
                if (visited[i])
                    continue;

                visited[i] = true;
                path.Add(nums[i]);
                BacktrackPermute(res, path, visited, nums);
                path.RemoveAt(path.Count - 1);
                visited[i] = false;
            }
        }

        /// <summary>
        /// leetcode  491  递增子序列(回溯)
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public IList<IList<int>> FindSubsequences(int[] nums)
        {
            IList<IList<int>> res = new List<IList<int>>();

            BacktrackFindSubsequences(res, new List<int>(), nums, 0);
            return res;
        }

        void BacktrackFindSubsequences(IList<IList<int>> res, List<int> path, int[] nums, int start)
        {
            if (path.Count >= 2)
                res.Add(new List<int>(path));
            if (start == nums.Length) return;

            HashSet<int> hash = new HashSet<int>();
            for (int i = start; i < nums.Length; i++)
            {
                if ((path.Count > 0 && nums[i] < path[path.Count - 1]) || hash.Contains(nums[i]))
                    continue;

                hash.Add(nums[i]);
                path.Add(nums[i]);
                BacktrackFindSubsequences(res, path, nums, i + 1);
                path.RemoveAt(path.Count - 1);
            }
        }


        /// <summary>
        /// leetcode  90  子集问题2(回溯)
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public IList<IList<int>> SubsetsWithDup(int[] nums)
        {
            IList<IList<int>> res = new List<IList<int>>();
            Array.Sort(nums);

            BacktrackSubsetsWithDup(res, new List<int>(), nums, 0);
            return res;
        }

        void BacktrackSubsetsWithDup(IList<IList<int>> res, List<int> path, int[] nums, int start)
        {
            res.Add(new List<int>(path));
            if (start == nums.Length)
            {
                return;
            }
            for (int i = start; i < nums.Length; i++)
            {
                if (i > start && nums[i - 1] == nums[i])
                    continue;

                path.Add(nums[i]);
                BacktrackSubsetsWithDup(res, path, nums, i + 1);
                path.RemoveAt(path.Count - 1);
            }
        }

        ///// <summary>
        ///// leetcode  78  子集问题
        ///// </summary>
        ///// <param name="nums"></param>
        ///// <returns></returns>
        //public IList<IList<int>> Subsets(int[] nums)
        //{
        //    IList<IList<int>> res = new List<IList<int>>();
        //    if (nums.Length > 0)
        //    {
        //        BacktrackSubsets(res, new Stack<int>(), nums, 0);
        //    }
        //    return res;
        //}

        //void BacktrackSubsets(IList<IList<int>> res, Stack<int> path, int[] nums, int start)
        //{
        //    res.Add(new List<int>(path));
        //    if (start == nums.Length)
        //    {
        //        return;
        //    }
        //    for (int i = start; i < nums.Length; i++)
        //    {
        //        path.Push(nums[i]);
        //        BacktrackSubsets(res, path, nums, i + 1);
        //        path.Pop();
        //    }
        //}

        /// <summary>
        /// leetcode  18  四数之和
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="target"></param>
        /// <returns></returns>
        public IList<IList<int>> FourSum(int[] nums, int target)
        {
            IList<IList<int>> res = new List<IList<int>>();
            int n = nums.Length;
            if (n < 4) return res;
            Array.Sort(nums);
            for (int i = 0; i < n; i++)
            {
                if (nums[i] > 0 && nums[i] >= target) break;
                if (i > 0 && nums[i] == nums[i - 1]) continue;

                for (int j = i + 1; j < n; j++)
                {
                    if (j > i + 1 && nums[j] == nums[j - 1]) continue;

                    int left = j + 1;
                    int right = n - 1;
                    while (left < right)
                    {
                        int sum = nums[i] + nums[j] + nums[left] + nums[right];
                        if (sum < target)
                        {
                            left++;
                        }
                        else if (sum > target)
                        {
                            right--;
                        }
                        else
                        {
                            res.Add(new List<int> { nums[i], nums[j], nums[left], nums[right] });

                            while (right > left && nums[right] == nums[right - 1]) right--;
                            while (right > left && nums[left] == nums[left + 1]) left++;

                            left++;
                            right--;
                        }
                    }
                }
            }
            return res;
        }

        /// <summary>
        /// leetcode  93  复原IP地址(回溯)
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public IList<string> RestoreIpAddresses(string s)
        {
            IList<string> res = new List<string>();
            if (s.Length <= 12 && s.Length >= 4)
            {
                BacktrackIP(res, new List<string>(), s, 0);
            }
            return res;
        }

        void BacktrackIP(IList<string> res, List<string> path, string s, int start)
        {
            if (path.Count == 4 && start == s.Length)
            {
                res.Add(string.Join('.', path.ToArray()));
                return;
            }
            for (int i = start; i < s.Length; i++)
            {
                if (s.Length - i < 4 - path.Count)
                {
                    break;
                }
                string temp = s.Substring(start, i - start + 1);
                if (IsIP(temp))
                {
                    path.Add(temp);
                    BacktrackIP(res, path, s, i + 1);
                    path.RemoveAt(path.Count - 1);
                }

            }
        }

        bool IsIP(string s)
        {
            if (s.Length == 1)
            {
                return true;
            }
            else if (s.Length == 2)
            {
                if (s[0] != '0')
                    return true;
            }
            else if (s.Length == 3)
            {
                if (s[0] != '0')
                {
                    if (int.Parse(s) <= 255)
                    {
                        return true;
                    }
                }
            }
            return false;
        }


        /// <summary>
        /// leetcode  131  分割回文串(回溯)
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public IList<IList<string>> Partition(string s)
        {
            IList<IList<string>> res = new List<IList<string>>();
            if (s.Length > 0)
            {
                BacktrackPartition(res, new List<string>(), s, 0);
            }
            return res;
        }

        void BacktrackPartition(IList<IList<string>> res, List<string> path, string s, int start)
        {
            if (start == s.Length)
            {
                res.Add(new List<string>(path));
                return;
            }
            for (int i = start; i < s.Length; i++)
            {
                string temp = s.Substring(start, i - start + 1);
                if (IsHuiWen(temp))
                {
                    path.Add(temp);
                    BacktrackPartition(res, path, s, i + 1);
                    path.RemoveAt(path.Count - 1);
                }
            }
        }

        bool IsHuiWen(string s)
        {
            if (s.Length <= 1) return true;
            int left = 0;
            int right = s.Length - 1;
            while (left < right)
            {
                if (s[left++] != s[right--])
                    return false;
            }
            return true;
        }


        /// <summary>
        /// leetcode  40  组合2(回溯)
        /// </summary>
        /// <param name="candidates"></param>
        /// <param name="target"></param>
        /// <returns></returns>
        public static IList<IList<int>> CombinationSum2(int[] candidates, int target)
        {
            IList<IList<int>> res = new List<IList<int>>();
            Array.Sort(candidates);
            BacktrackCombineSum2(res, new List<int>(), candidates, target, 0, 0);
            return res;
        }

        static void BacktrackCombineSum2(IList<IList<int>> res, List<int> path, int[] candidates, int target, int sum, int start)
        {
            if (sum == target)
            {
                res.Add(new List<int>(path));
                return;
            }
            for (int i = start; i < candidates.Length; i++)
            {
                if (sum + candidates[i] > target) break;
                if (i > start && candidates[i] == candidates[i - 1])
                {
                    continue;
                }

                path.Add(candidates[i]);
                BacktrackCombineSum2(res, path, candidates, target, sum + candidates[i], i + 1);
                path.RemoveAt(path.Count - 1);
            }
        }

        /// <summary>
        /// leetcode  39  组合(回溯)
        /// </summary>
        /// <param name="candidates"></param>
        /// <param name="target"></param>
        /// <returns></returns>
        public static IList<IList<int>> CombinationSum(int[] candidates, int target)
        {
            IList<IList<int>> res = new List<IList<int>>();
            Array.Sort(candidates);
            BacktrackCombineSum1(res, new List<int>(), candidates, target, 0, 0);
            return res;
        }

        static void BacktrackCombineSum1(IList<IList<int>> res, List<int> path, int[] candidates, int target, int sum, int start)
        {
            if (sum == target)
            {
                res.Add(new List<int>(path));
                return;
            }
            for (int i = start; i < candidates.Length; i++)
            {
                if (sum + candidates[i] > target) break;
                path.Add(candidates[i]);
                BacktrackCombineSum1(res, path, candidates, target, sum + candidates[i], i);
                path.RemoveAt(path.Count - 1);
            }
        }

        /// <summary>
        /// leetcode  17  电话号码的字母组合
        /// </summary>
        /// <param name="digits"></param>
        /// <returns></returns>
        public static IList<string> LetterCombinations(string digits)
        {
            IList<string> res = new List<string>();
            if (digits.Length == 0)
            {
                return res;
            }
            Dictionary<char, string> dict = new Dictionary<char, string>();
            dict.Add('2', "abc");
            dict.Add('3', "def");
            dict.Add('4', "ghi");
            dict.Add('5', "jkl");
            dict.Add('6', "mno");
            dict.Add('7', "pqrs");
            dict.Add('8', "tuv");
            dict.Add('9', "wxyz");

            DFSLetterCombine(res, dict, new StringBuilder(), digits, 0);

            return res;
        }
        public static void DFSLetterCombine(IList<string> res, Dictionary<char, string> dict, StringBuilder sb, string digits, int k)
        {
            if (k == digits.Length)
            {
                res.Add(sb.ToString());
                return;
            }
            foreach (var ch in dict[digits[k]])
            {
                sb.Append(ch);
                DFSLetterCombine(res, dict, sb, digits, k + 1);
                sb.Remove(digits.Length - 1, 1);
            }
        }

        /// <summary>
        /// leetcode  77  组合
        /// </summary>
        /// <param name="n"></param>
        /// <param name="k"></param>
        /// <returns></returns>
        public static IList<IList<int>> CombineOld(int n, int k)
        {
            IList<IList<int>> res = new List<IList<int>>();
            Stack<int> path = new Stack<int>();
            BacktrackCombine(res, path, n, k, 1);
            return res;


            void BacktrackCombine(IList<IList<int>> res, Stack<int> path, int n, int k, int start)
            {
                if (path.Count == k)
                {
                    res.Add(new List<int>(path));
                    return;
                }
                for (int i = start; i <= n - (k - path.Count) + 1; i++)
                {
                    path.Push(i);
                    BacktrackCombine(res, path, n, k, i + 1);
                    path.Pop();
                }
            }
        }

        /// <summary>
        /// leetcode  216  组合总和3
        /// </summary>
        /// <param name="k"></param>
        /// <param name="n"></param>
        /// <returns></returns>
        public IList<IList<int>> CombinationSum3Old(int k, int n)
        {
            IList<IList<int>> res = new List<IList<int>>();
            if (k <= n)
            {
                Stack<int> path = new Stack<int>();
                BacktrackCombinationSum3(res, path, 0, 1, k, n);
            }
            return res;
        }

        void BacktrackCombinationSum3(IList<IList<int>> res, Stack<int> path, int sum, int start, int k, int n)
        {
            if (path.Count == n && sum == n)
            {
                res.Add(new List<int>(path));
                return;
            }
            // path.Count+n-i+1 < k
            for (int i = start; i <= 9; i++)
            {
                path.Push(i);
                sum += i;
                BacktrackCombinationSum3(res, path, sum, i + 1, k, n);
                sum -= path.Pop();
            }
        }
    }
}
